'''
https://leetcode.cn/problems/palindrome-linked-list/description/
'''
from typing import Optional

from c03_list.utils import ListNode, generate_list


class Solution:
    def isPalindrome_forceSolution(self, head: Optional[ListNode]) -> bool:
        cur = head
        list = []
        while cur:
            list.append(cur.val)
            cur = cur.next
        return list == list[::-1]

    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head or not head.next: return True
        def reverse(head):
            prev = None
            while head:
                next = head.next
                head.next = prev
                prev = head
                head = next
            return prev
        s, f  = head, head
        while f.next and f.next.next:
            s = s.next
            f = f.next.next
        # 反转后半部分
        new_head = reverse(s.next)
        i, j = head, new_head
        while i and j:
            if i.val != j.val: return False
            i, j = i.next, j.next
        # 还原链表
        return True

arr = [1,2]
list1 = generate_list(arr)
v = Solution().isPalindrome(list1)
print(v)